package LeetCode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName interview
 * @Description: TODO
 * @date ${DAT}22:15
 */
public class LeetCode46 {


    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> lists = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        if (nums.length == 0){
            return lists;
        }
        List<Integer> p = new ArrayList<>();
        generatePermutation(nums,0,p,used,lists);
        return lists;
    }

    /**
     *
     * @param nums 原数组
     * @param index 下标
     * @param p 辅助数组 存储一个排列
     */
    public void generatePermutation(int[] nums,int index,List<Integer> p,boolean[] userd, List<List<Integer>> lists){
        if (index == nums.length){
            //此时的结果会是空值
            /*
            path 这个变量所指向的对象在递归的过程中只有一份，深度优先遍历完成以后，因为回到了根结点（因为我们之前说了，从深层结点回到浅层结点的时候，需要撤销之前的选择），因此 path 这个变量回到根结点以后都为空。
            在 Java 中，因为都是值传递，对象类型变量在传参的过程中，复制的都是变量的地址。（Python 我不是很清楚 Python 中方法变量的传递机制，所以暂时没有写，欢迎知道的朋友补充，但是从实验的结果上看和 Java 很像。）这些地址被添加到 res 变量，但实际上指向的是同一块内存地址，因此我们会看到 6 个空的列表对象。解决的方法很简单，在 res.add(path); 这里做一次拷贝即可。
             */
            lists.add(new ArrayList<>(p));
            return;
        }

        for (int i = 0; i < nums.length; i++){
            /**
             * !userd[i - 1] 是为了保证[1,1]能够进行，就会把不该剪的剪掉 前一个必须是true
             */
            if (!userd[i]){
                p.add(nums[i]);
                userd[i] = true;
                generatePermutation(nums,index + 1,p,userd,lists);
                //在删除的时候因为这边是值传递，会直接影响之前的存储，所以在存储的时候创建一个新的地址就行了
                p.remove(p.size() - 1);
                userd[i] = false;
            }
        }
    }

    public static void main(String[] args) {
        List<List<Integer>> res = new LeetCode46().permute(new int[]{1,2,3});
        for (List<Integer> re : res) {
            String s = "";
            for (Integer integer : re) {
                 s += (integer + "");
            }
            int res3 = Integer.parseInt(s);
            System.out.println(res3);
        }

    }

    List<List<Integer>> res2 = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        if (nums.length == 0) {
            return res2;
        }
        List<Integer> list = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        getNums(nums,0,nums.length,list,used);
        return res2;
    }

    public void getNums(int[] nums,int index,int len,List<Integer> list,boolean[] used){
        if (index >= len){
            res2.add(new ArrayList<>(list));
            return;
        }

        for (int i = 0; i < len; i++){
            if (!used[i]){
                used[i] = true;
                list.add(nums[i]);
                getNums(nums,index + 1,len,list,used);
                list.remove(list.size() - 1);
                used[i] = false;
            }
        }
    }


}
